home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / util / libs / type1beta5.lha / type1 / src / curves.c < prev    next >
C/C++ Source or Header  |  1994-12-17  |  8KB  |  253 lines
  1. /* $XConsortium: curves.c,v 1.3 91/10/10 11:17:56 rws Exp $ */
  2. /* Copyright International Business Machines,Corp. 1991              */
  3. /* All Rights Reserved                                               */
  4.  
  5. /* License to use, copy, modify, and distribute this software        */
  6. /* and its documentation for any purpose and without fee is          */
  7. /* hereby granted, provided that licensee provides a license to      */
  8. /* IBM, Corp. to use, copy, modify, and distribute derivative        */
  9. /* works and their documentation for any purpose and without         */
  10. /* fee, that the above copyright notice appear in all copies         */
  11. /* and that both that copyright notice and this permission           */
  12. /* notice appear in supporting documentation, and that the name      */
  13. /* of IBM not be used in advertising or publicity pertaining to      */
  14. /* distribution of the software without specific, written prior      */
  15. /* permission.                                                       */
  16.  
  17. /* IBM PROVIDES THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES        */
  18. /* OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT        */
  19. /* LIMITED TO ANY IMPLIED WARRANTIES OF MERCHANTABILITY,             */
  20. /* FITNESS FOR A PARTICULAR PURPOSE, AND NONINFRINGEMENT OF          */
  21. /* THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE QUALITY AND        */
  22. /* PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT        */
  23. /* OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF      */
  24. /* THE SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM) ASSUMES      */
  25. /* THE ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN      */
  26. /* NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR         */
  27. /* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING         */
  28. /* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF        */
  29. /* CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT        */
  30. /* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS           */
  31. /* SOFTWARE.                                                         */
  32. /*
  33.  
  34. /*
  35.  * CURVES Module - Stepping Beziers
  36.  *
  37.  * This module is responsible for "rasterizing"
  38.  * Bezier third order curves.  That is, it changes the high level curve
  39.  * specification into a list of pels that that curve travels through.
  40.  */
  41.  
  42.  
  43. /**
  44.  * Includes
  45.  **/
  46. #ifndef T1GST
  47. #include "global.h"
  48. #endif
  49.  
  50.  
  51. /**
  52.  * Local prototypes
  53.  **/
  54. static int BezierTerminationTest(fractpel xa, fractpel ya, fractpel xb, fractpel yb, fractpel xc, fractpel yc, fractpel xd, fractpel yd);
  55. static struct segment *StepBezierRecurse(struct bezierinfo *I, fractpel xA, fractpel yA, fractpel xB, fractpel yB, fractpel xC, fractpel yC, fractpel xD, fractpel yD);
  56.  
  57.  
  58. /**
  59.  * The "bezierinfo" Structure
  60.  *
  61.  * This structure is used to store information used when we subdivide
  62.  * Bezier curves.
  63.  **/
  64. struct bezierinfo
  65. {
  66.     struct region *region;    /* the region being built or NULL             */
  67.     struct fractpoint last;    /* not used yet; maybe could save some work  */
  68.     struct fractpoint origin;    /* the origin of the bezier                */
  69. };
  70.  
  71.  
  72. /*
  73.  * Checking for termination of the subdivision process:
  74.  * This is the stupidest test in the world, just check if the coordinatewise
  75.  * distance from an end control point to the next control point is less than
  76.  * one half pel.   If so, we must be done.
  77.  * This returns 1 if the subdivision is terminated and 0 if you still need
  78.  * to subdivide.
  79.  */
  80. //
  81. //NOTE: 4/26/93 AMISH
  82. //I'm marking this function static, since it is.
  83. //
  84. //static int BezierTerminationTest(fractpel xa, fractpel ya, fractpel xb, fractpel yb,
  85. //                            fractpel xc, fractpel yc, fractpel xd, fractpel yd)
  86. //{
  87. //    fractpel dmax;
  88. //
  89. //    dmax = ABS(xa - xb);
  90. //    dmax = MAX(dmax, ABS(ya - yb));
  91. //    dmax = MAX(dmax, ABS(xd - xc));
  92. //    dmax = MAX(dmax, ABS(yd - yc));
  93. //    if (dmax > FPHALF)
  94. //        return (0);    /* not done yet */
  95. //    else
  96. //        return (1);    /* done */
  97. //}
  98.  
  99. /**
  100.  * REWRITTEN BY AMISH:
  101.  * The original routine is rather silly.  It does many more comparisons
  102.  * than we care about.  Profiling revealed that this routine is called
  103.  * very frequently, and it was very inefficient
  104.  * 20-April-93
  105.  **/
  106. static int BezierTerminationTest(fractpel xa, fractpel ya, fractpel xb, fractpel yb,
  107.                             fractpel xc, fractpel yc, fractpel xd, fractpel yd)
  108. {
  109.     if (ABS(xa-xb) > FPHALF)
  110.         return 0;
  111.  
  112.     if (ABS(ya-yb) > FPHALF)
  113.         return 0;
  114.  
  115.     if (ABS(xd-xc) > FPHALF)
  116.         return 0;
  117.  
  118.     if (ABS(yd-yc) > FPHALF)
  119.         return 0;
  120.  
  121.     return 1;    /* Done */
  122. }
  123.  
  124.  
  125. /*
  126.  * StepBezierRecurse() - The Recursive Logic in StepBezier()
  127.  *
  128.  * The recursion involves dividing the control polygon into two smaller
  129.  * control polygons by finding the midpoints of the lines.  This idea is
  130.  * described in any graphics text book and its simplicity is what caused
  131.  * Bezier to define his curves as he did.  If the input region 'R' is NULL,
  132.  * the result is a path that is the 'flattened' curve; otherwise StepBezier
  133.  * returns nothing special.
  134.  */
  135. /*
  136.  * Note that "stepping" and "flattening" are so similiar that they use the
  137.  * same routine.  When the "region" parameter is NULL, that is a flag that
  138.  * we are flattening instead of stepping.
  139.  */
  140. static struct segment *StepBezierRecurse(
  141.         struct bezierinfo *I,        /* Region under construction, or NULL */
  142.         fractpel xA, fractpel yA,    /* A control point */
  143.         fractpel xB, fractpel yB,    /* B control point */
  144.         fractpel xC, fractpel yC,    /* C control point */
  145.         fractpel xD, fractpel yD)    /* D control point */
  146. {
  147.     if (BezierTerminationTest(xA, yA, xB, yB, xC, yC, xD, yD))
  148.     {
  149.         if (I->region == NULL)
  150.             return (PathSegment(LINETYPE, xD - xA, yD - yA));
  151.         else
  152.             StepLine(I->region, I->origin.x + xA, I->origin.y + yA,
  153.                  I->origin.x + xD, I->origin.y + yD);
  154.     }
  155.     else
  156.     {
  157.         fractpel xAB, yAB;
  158.         fractpel xBC, yBC;
  159.         fractpel xCD, yCD;
  160.         fractpel xABC, yABC;
  161.         fractpel xBCD, yBCD;
  162.         fractpel xABCD, yABCD;
  163.  
  164.         xAB = xA + xB;
  165.         yAB = yA + yB;
  166.         xBC = xB + xC;
  167.         yBC = yB + yC;
  168.         xCD = xC + xD;
  169.         yCD = yC + yD;
  170.  
  171.         xABC = xAB + xBC;
  172.         yABC = yAB + yBC;
  173.         xBCD = xBC + xCD;
  174.         yBCD = yBC + yCD;
  175.  
  176.         xABCD = xABC + xBCD;
  177.         yABCD = yABC + yBCD;
  178.  
  179.         xAB >>= 1;
  180.         yAB >>= 1;
  181.         xBC >>= 1;
  182.         yBC >>= 1;
  183.         xCD >>= 1;
  184.         yCD >>= 1;
  185.         xABC >>= 2;
  186.         yABC >>= 2;
  187.         xBCD >>= 2;
  188.         yBCD >>= 2;
  189.         xABCD >>= 3;
  190.         yABCD >>= 3;
  191.  
  192.         if (I->region == NULL)
  193.         {
  194.             return (Join(
  195.                         StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD),
  196.                         StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD)
  197.                 )
  198.                 );
  199.         }
  200.         else
  201.         {
  202.             StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD);
  203.             StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD);
  204.         }
  205.     }
  206.     /*NOTREACHED*/
  207. }
  208.  
  209.  
  210. /*
  211.  * TOOBIG() - Macro to Test if a Coordinate is Too Big to Bezier SubDivide Normally
  212.  *
  213.  * Intermediate values in the Bezier subdivision are 8 times bigger than
  214.  * the starting values.  If this overflows, a 'long', we are in trouble:
  215.  */
  216. #define  BITS         (sizeof(long)*8)
  217. #define  HIGHTEST(p)  (((p)>>(BITS-4)) != 0)    /* includes sign bit */
  218. #define  TOOBIG(xy)   ((xy < 0) ? HIGHTEST(-xy) : HIGHTEST(xy))
  219.  
  220.  
  221. /*
  222.  * StepBezier() - Produce Run Ends for a Bezier Curve
  223.  *
  224.  * This is the entry point called from outside the module.
  225.  */
  226. struct segment *StepBezier(
  227.         struct region *R,        /* Region under construction or NULL */
  228.         fractpel xA, fractpel yA,    /* A control point */
  229.         fractpel xB, fractpel yB,    /* B control point */
  230.         fractpel xC, fractpel yC,    /* C control point */
  231.         fractpel xD, fractpel yD)    /* D control point */
  232. {
  233.     struct bezierinfo Info;
  234.  
  235.     Info.region = R;
  236.     Info.origin.x = xA;
  237.     Info.origin.y = yA;
  238.  
  239.     xB -= xA;
  240.     xC -= xA;
  241.     xD -= xA;
  242.     yB -= yA;
  243.     yC -= yA;
  244.     yD -= yA;
  245.  
  246.     if (TOOBIG(xB) || TOOBIG(yB) || TOOBIG(xC) || TOOBIG(yC)
  247.         || TOOBIG(xD) || TOOBIG(yD))
  248.         t1_abort("Beziers this big not yet supported");
  249.  
  250.     return (StepBezierRecurse(&Info,
  251.                (fractpel) 0, (fractpel) 0, xB, yB, xC, yC, xD, yD));
  252. }
  253.